//==========================================================================
// Copyright (c) 2000-2008,  Elastos, Inc.  All Rights Reserved.
//==========================================================================
#ifndef __ELA_RBTREE_H
#define __ELA_RBTREE_H

#define NULL 0

struct rb_node
{
    struct rb_node *rb_left; /* left element */
    struct rb_node *rb_right; /* right element */
    struct rb_node *rb_parent; /* parent element */
    int rb_color;   /* node color */
};

struct rb_root
{
    struct rb_node *rb_node; /* root of the tree */
};

#define RB_ROOT ((struct rb_root){NULL})
#define rb_entry(p, container, field)  \
    ((container *) ((char *)p - ((char *)&(((container *)(char *)0)->field))))

#define RB_BLACK 0
#define RB_RED  1

extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);

/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(struct rb_node *);
extern struct rb_node *rb_prev(struct rb_node *);
extern struct rb_node *rb_first(struct rb_root *);

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                struct rb_node ** rb_link)
{
    node->rb_parent = parent;
    node->rb_color = RB_RED;
    node->rb_left = node->rb_right = NULL;

    *rb_link = node;
}

#endif /* __ELA_RBTREE_H__ */
